package dataStructure.LinkList;

/*循环链表  解决约瑟夫环问题*/
public interface CircleLinkList {
    // 返回头节点
    CNode  getHead();
    // 头插法  逆序添加
    void addFirst(int data);

    // 尾插法 顺序添加
    void addLast(int data);

    // 任意位置插入，第一数据节点为0号下标
    boolean addIndex(int index, int data);

    // 查找是否包含关键字 key 在单链表中
    boolean contains(int data);
    // 按值查询
    CNode searchNodeByData(int data);

    // 删除第一次出现的关键字为 key 的节点
    boolean remove(int data);

    // 删除所有值为 key 的节点
    void removeAllKey(int data);

    boolean updateNodeByIndex(int index,int data);

    // 得到单链表的长度
    int size();

    // 打印单链表
    void display();

    // 清空单链表以防内存泄漏
    void clear();

    CNode acquireLastNode();

    // 找最小值节点
    CNode searchMinNode ();

    // 找最小值的前驱节点
    CNode getMinNodePre();
    // 根据索引找节点
    CNode searchNodeByIndex(int index);

    void countCNode(int startNo, int countNum, int nums);
}
class CLinkList implements CircleLinkList{
    private CNode Chead = null;

    
    @Override
    public CNode getHead() {
        return null;
    }

    @Override
    public void addFirst(int data) {

    }
    
    /*nums 是插入的个数 为了模拟约瑟夫环问题*/
    @Override
    public void addLast(int nums) {
        // 实现添加
        // nums 做一个数据校验
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        CNode temp = null; // 辅助指针，帮助构建环形链表
        // 使用for来创建我们的环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号，创建节点
            CNode node = new CNode(i);
            // 如果是第一个节点
            if (i == 1) {
                Chead = node;
                Chead.setNext(Chead); // 构成环
                temp = Chead; // 让curBoy指向第一个节点
            } else {
                temp.setNext(node);
                node.setNext(Chead);
                temp = node;
            }
        }
    }

    @Override
    public boolean addIndex(int index, int data) {
        return false;
    }

    @Override
    public boolean contains(int data) {
        return false;
    }

    @Override
    public CNode searchNodeByData(int data) {
        return null;
    }

    @Override
    public boolean remove(int data) {
        return false;
    }

    @Override
    public void removeAllKey(int data) {

    }

    @Override
    public boolean updateNodeByIndex(int index, int data) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void display() {
        // 实现 展示
        // 判断链表是否为空
        if (Chead == null) {
            System.out.println("没有任何节点~~");
            return;
        }
        // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        CNode cur = Chead;
        while (true) {
            System.out.printf("节点的值 %d \n", cur.getData());
            if (cur.getNext() == Chead) {// 说明已经遍历完毕
                break;
            }
            cur = cur.getNext(); // 后移
        }
    }

    // 根据用户的输入，计算节点出圈的顺序
    /**
     *
     * @param startNo
     *            表示从第几个节点开始数数
     * @param countNum
     *            表示数几下
     * @param nums
     *            表示最初有多少节点在圈中
     */
    @Override
    public void countCNode(int startNo, int countNum, int nums) {
        // 先对数据进行校验   nums只是起到一个限制startNo的作用
        if (Chead == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误， 请重新输入");
            return;
        }
        // 创建要给辅助指针,帮助完成节点出圈
        CNode helper = Chead;
        // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
        while (true) {
            if (helper.getNext() == Chead) { // 说明helper指向最后节点
                break;
            }
            helper = helper.getNext();
        }
        //节点报数前，先让 Chead 和  helper 移动 k - 1次
        for(int j = 0; j < startNo - 1; j++) {
            Chead = Chead.getNext();
            helper = helper.getNext();
        }
        //当节点报数时，让first 和 helper 指针同时 的移动  m  - 1 次, 然后出圈
        //这里是一个循环操作，知道圈中只有一个节点
        while(true) {
            if(helper == Chead) { //说明圈中只有一个节点
                break;
            }
            //让 Chead 和 helper 指针同时 的移动 countNum - 1
            for(int j = 0; j < countNum - 1; j++) {
                Chead = Chead.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点，就是要出圈的节点
            System.out.printf("节点%d出圈\n", Chead.getData());
            //这时将first指向的节点出圈
            Chead = Chead.getNext();
            helper.setNext(Chead); //

        }
        System.out.printf("最后留在圈中的节点编号%d \n", Chead.getData());

    }
    
    @Override
    public void clear() {

    }

    @Override
    public CNode acquireLastNode() {
        return null;
    }

    @Override
    public CNode searchMinNode() {
        return null;
    }

    @Override
    public CNode getMinNodePre() {
        return null;
    }

    @Override
    public CNode searchNodeByIndex(int index) {
        return null;
    }
}

class CNode{
    private int data;
    public CNode next; //指向下一个节点
    //构造器
    public CNode(){

    }
    public CNode(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public CNode getNext() {
        return next;
    }

    public void setNext(CNode next) {
        this.next = next;
    }

    public void setData(int data) {
        this.data = data;
    }

    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        // 为什么里面不写next , 因为输出每个节点都会把后面的也输出
        return "CNode [data=" + data +"]";
    }
}

class testC {
    public static void main(String[] args) {
        System.out.println("环形链表");

        CircleLinkList circleLinkList = new CLinkList();
        circleLinkList.addLast(10);
        circleLinkList.display();
        System.out.println("约瑟夫测试");
        circleLinkList.countCNode(1,5,5);

    }
}